//
//  queueImp.c
//  Chapter_1
//
//  Created by hao on 18/3/23.
//  Copyright © 2018年 hao. All rights reserved.
//

#include "queueImp.h"

QueueList createQueueList()
{
    QueueNode node = (QueueNode)malloc(sizeof(struct SinglyLinkedNode));
    node->next = TPL_LIST_NULL;
    QueueList list = (QueueList)malloc(sizeof(struct QueueL));
    list->fornt = list->rear = TPL_LIST_NULL;
    return list;
}

void addValueInQueue(ElementType elem, QueueList queue)
{
    // 创建一个节点，添加到队列
    QueueNode node = (QueueNode)malloc(sizeof(struct SinglyLinkedNode));
    node->next = TPL_LIST_NULL;
    node->data = elem;
    if (queue->fornt == TPL_LIST_NULL) {
        // 如果队首为空就指向新创建的节点
        queue->fornt = node;
        queue->fornt->next = TPL_LIST_NULL;
    }
    if (queue->rear == TPL_LIST_NULL) {
        // 队尾为空也指向新创建的节点
        queue->rear = node;
        queue->rear->next = TPL_LIST_NULL;
    } else {
        // 获得最后一个节点next指向新创建的node
        queue->rear->next = node;
        // 添加完成后将队尾指向新节点
        queue->rear = node;
    }
}

ElementType deleteInQueue(QueueList queue)
{
    // 判断队列队首是不是空
    if (queue->fornt == TPL_LIST_NULL) {
        printf("删除队列为空 \n");
        return TPL_NOT_FOUND;
    }
    QueueNode firstNode = queue->fornt;
    // 还得判断队列是不是只有一个元素
    if (queue->fornt == queue->rear) {
        // 删除后列表就要置空
        queue->fornt = queue->rear = TPL_LIST_NULL;
    } else {
        // 将firstNode的下一个节点赋值给队首
        queue->fornt = firstNode->next;
    }
    ElementType res = firstNode->data;
    free(firstNode);
    return res;
}

#pragma mark - 多项式乘法与加法运算
void attach(int coeff, int exp, PolynomialNode *result)
{
    PolynomialNode addPoly = malloc(sizeof(struct PolyNode));
    addPoly->coeff = coeff;
    addPoly->exp = exp;
    addPoly->next = TPL_LIST_NULL;
    if (*result == TPL_LIST_NULL) {
        *result = addPoly;
    } else {
        (*result)->next = addPoly;
        *result = addPoly;
    }
}

// 两个参数分别代表一个多项式
PolynomialNode polyAdd(PolynomialNode poly1, PolynomialNode poly2)
{
    PolynomialNode temp = malloc(sizeof(struct PolyNode));
    PolynomialNode rearPoly = temp; // 指向尾部多项式
    PolynomialNode resultPoly = rearPoly;
    
    // 只要有一项为空就跳出循环
    while (poly1 != TPL_LIST_NULL && poly2 != TPL_LIST_NULL) {
        // 比较指数，指数大的直接添加到结果多项式中，相等两个系数相加，指针指向next
        int p1Exp = poly1->exp;
        int p2Exp = poly2->exp;
        if (p1Exp > p2Exp) {
            attach(poly1->coeff, p1Exp, &rearPoly);
            poly1 = poly1->next;
        } else if (p1Exp < p2Exp) {
            attach(poly2->coeff, p2Exp, &rearPoly);
            poly2 = poly2->next;
        } else if (p1Exp == p2Exp) {
            // 指数相同，系数相加
            int coeff = poly1->coeff+poly2->coeff;
            if (coeff != 0) {
                attach(coeff, p1Exp, &rearPoly);
            }
            poly1 = poly1->next;
            poly2 = poly2->next;
        }
    }
    // 跳出循环后还要遍历一下剩下的多项式直接添加到结果多项式当中
    for (; poly1 != TPL_LIST_NULL; poly1 = poly1->next) {
        attach(poly1->coeff, poly1->exp, &rearPoly);
    }
    for (; poly2 != TPL_LIST_NULL; poly2 = poly2->next) {
        attach(poly2->coeff, poly2->exp, &rearPoly);
    }
    // 最后指向NULL
    rearPoly->next = TPL_LIST_NULL;
    resultPoly = resultPoly->next;
    free(temp);
    return resultPoly;
}

void prinftPolynomial(PolynomialNode poly)
{
    printf("polynomial = ");
    int i = 0;
    while (poly != TPL_LIST_NULL) {
        if (i > 0 && poly->coeff > 0) {
            printf("+");
        }
        if (poly->exp == 0) {
            printf("%d", poly->coeff);
        } else {
            printf("%dX%d", poly->coeff, poly->exp);
        }
        poly = poly->next;
        i++;
    }
    printf("\n");
}

PolynomialNode createPolynomialList(int coeffs[], int exps[], int items)
{
    PolynomialNode p = malloc(sizeof(struct PolyNode));
    PolynomialNode rearPoly = p; // 指向最后一个多项式的指针
    p->next = TPL_LIST_NULL;
    for (int i = 0; i < items; i++) {
        if (i == 0) {
            p->coeff = coeffs[i];
            p->exp = exps[i];
        } else {
            PolynomialNode temp = malloc(sizeof(struct PolyNode));
            temp->coeff = coeffs[i];
            temp->exp = exps[i];
            // 添加到队尾
            rearPoly->next = temp;
            // 队尾后移
            rearPoly = temp;
            // 下面两句是栈操作
//            temp->next = p;
//            p = temp;
        }
    }
    return p;
}







